/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

package minpath.bellmanford;

import static aux.General.infinity;
import static aux.General.extractWeight;
import aux.MinHeap;
import base.JGrafo;
import base.Vertice;
import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.HashMap;

/**
 *
 * @author diego
 */
public class BellmanFord {
    public static HashMap<Vertice, ArrayList<Vertice>> bellmanFord (JGrafo G, HashMap<AbstractMap.SimpleEntry<Vertice, Vertice>, Integer> weights, Vertice s) {
        HashMap<Vertice, ArrayList<Vertice>> S = new HashMap<>();
        HashMap<Vertice, Vertice> P = new HashMap <>();
        
        // Passo inicial
        for (Vertice v : G.vertices) {
            v.key = infinity;
            P.put(v, null);
        }
        s.key = 0;
        
        // Relaxando arestas
        for (int i = 1; i < G.vertices.size(); i ++) {
            for (Vertice u : G.vertices) {
                for (Vertice v : G.adjacencies(u)) {
                    if (v.key > (u.key + extractWeight(u, v, weights))) {
                        v.key = (u.key + extractWeight(u, v, weights));
                        P.put(v, u);
                    }
                }
            }
        }
        
        // Procurando por ciclos negativos
        for (Vertice u : G.vertices) {
            Vertice v = u;
            ArrayList<Vertice> path = new ArrayList<Vertice>();
            while (P.get(v) != null) {
                path.add(v);
                v = P.get(v);
            }
            S.put(u, path);
        }
        
        return S;
    }
}
